/* 计数排序 */

#include<iostream>
#include<algorithm>
#include<random>
using namespace std;

int main(void)
{
	constexpr int MAXVALUE = 10;		//0 ~ 9
	int a[20];
	mt19937 g;

	generate(a, a + 20, [&g](void) -> int {return g() % 10;});
	for_each(a, a + 20, [](int e) -> void {cout<< e << " ";});
	cout<< endl;

	int valueCount[MAXVALUE]{0};
	for (int i = 0; i < 20; i++)
	{
		int value = a[i];

		//valueCount[i]的意义：等于i的数有几个？
		valueCount[value]++;
	}

	for (int j = 1; j < MAXVALUE; j++)
	{
		//现在valueCount[i]的意义是：<= i的数有几个？
		valueCount[j] = valueCount[j] + valueCount[j - 1];
	}

	int sortRes[20];
	for (int i = 19; i >= 0; i--)
	{
		int value = a[i];
		//<= a[i]的数有几个？
		int count = valueCount[value];
		//假设<= a[i]的数有5个，那么排序后最后一个a[i]的位置为4
		//从后往前选择元素，可以保证稳定排序
		sortRes[--count] = value;
		valueCount[value] = count;
	}

	for_each(sortRes, sortRes + 20, [](int e) -> void {cout<< e << " ";});
	cout<< endl;

	return 0;
}
